W1054 永无止境的反转
1 Description
给定一条长度为
举例来说,若数轴为
你的任务是在每次操作后,求出当前还有多少白色块。注意,每次操作将会永久地改变数轴。
2 Input
其中
接下来
2.1 数据范围
为整数。 。 。
3 Output
- 表示每次操作后,当前数轴上有多少白点。
4 示例
Sample Input 1
10 3
1 7
3 9
5 10
Sample Output 1
3
6
4
5 Hint
操作序列:
Solution
详情:关于本题的回答
线段树+离散化
其实离散化+线段树就可以解决了! 将
#include<bits/stdc++.h>
#define int long long
using namespace std;
#define lc root<<1
#define rc root<<1|1
struct Node {
int l, r;
int len;
int white;
bool flip;
};
const int MAX_NODES = 4 * 400000; // 足够大的节点数,防止越界
Node tree[MAX_NODES];
vector<int> p;
void build(int root, int l, int r) {
int len = p[l + 1] - p[l];
tree[root] = {l,r,len,len,false};
if (l == r) {
return;
}
int mid = (l + r) / 2;
build(lc, l, mid);
build(rc, mid + 1, r);
tree[root].len = tree[lc].len + tree[rc].len;
tree[root].white = tree[lc].white + tree[rc].white;
}
void push(int root) {
if (tree[root].flip && tree[root].l != tree[root].r) {
for (int child : {lc, rc}) {
tree[child].flip = !tree[child].flip;
tree[child].white = tree[child].len - tree[child].white;
}
tree[root].flip = false;
}
}
void update(int root, int l, int r) {
if (tree[root].r < l || tree[root].l > r) {
return;
}
if (l <= tree[root].l && tree[root].r <= r) {
tree[root].flip = !tree[root].flip;
tree[root].white = tree[root].len - tree[root].white;
return;
}
push(root);
update(lc, l, r);
update(rc, l, r);
tree[root].white = tree[lc].white + tree[rc].white;
}
signed main() {
ios::sync_with_stdio(false);cin.tie(0);
int n, m;
cin >> n >> m;
p.push_back(1);
p.push_back(n + 1);
vector<pair<int, int>> ops;
for (int i = 0; i < m; ++i) {
int l, r;
cin >> l >> r;
ops.emplace_back(l, r);
p.push_back(l);
p.push_back(r + 1);
}
sort(p.begin(), p.end());
auto last = unique(p.begin(), p.end());
p.erase(last, p.end());
int siz = p.size() - 1;
if (siz == 0) {
for (int i = 0; i < m; ++i) {
cout << "0\n";
}
return 0;
}
build(1, 0, siz - 1);
for (auto& op : ops) {
int l = op.first;
int r = op.second;
int i = lower_bound(p.begin(), p.end(), l) - p.begin();
int j = lower_bound(p.begin(), p.end(), r + 1) - p.begin();
if (i < j) {
update(1, i, j - 1);
}
cout << tree[1].white << '\n';
}
return 0;
}
区间分段管理
如果区间存在重叠,则将区间分为三个部分,否则保留原区间
代码:
By Gemini 2.0 Flash Thinking Experimental 01-21
#include <iostream>
#include <vector>
#include <map>
using namespace std;
int main() {
long long n; // 数轴长度
int m; // 操作次数
cin >> n >> m;
map<long long, bool> seg; // 区间颜色,key: 区间起点, value: true=白色, false=黑色
seg[1] = true; // 初始整个区间 [1, n] 为白色
for (int i = 0; i < m; ++i) {
long long l, r; // 操作区间 [l, r]
cin >> l >> r;
map<long long, bool> nseg; // 操作后的新区间颜色
for (auto const& [st, color] : seg) { // 遍历当前所有区间
long long cur_st = st; // 当前区间起点
long long cur_ed; // 当前区间终点
auto it = seg.upper_bound(st); // 找到下一个区间的起点
if (it == seg.end()) {
cur_ed = n; // 如果没有下一个区间,则当前区间延伸到数轴末尾
} else {
cur_ed = it->first - 1; // 否则,当前区间终点是下一个区间的起点 - 1
}
long long ol_st = max(cur_st, l); // 重叠区间起点
long long ol_ed = min(cur_ed, r); // 重叠区间终点
if (ol_st <= ol_ed) { // 如果有重叠
if (cur_st < ol_st) { // 当前区间在重叠区间之前的部分
nseg[cur_st] = color; // 颜色不变
}
nseg[ol_st] = !color; // 重叠区间颜色反转
if (ol_ed < cur_ed) { // 当前区间在重叠区间之后的部分
nseg[ol_ed + 1] = color; // 颜色不变
}
} else { // 如果没有重叠
nseg[cur_st] = color; // 整个区间颜色不变
}
}
seg = nseg; // 更新区间颜色
long long cnt = 0; // 白色块数量
for (auto const& [st, color] : seg) {
if (color) { // 如果是白色区间
long long cur_st = st;
long long cur_ed;
auto it = seg.upper_bound(st);
if (it == seg.end()) {
cur_ed = n;
} else {
cur_ed = it->first - 1;
}
cnt += (cur_ed - cur_st + 1); // 累加白色块长度
}
}
cout << cnt << '\n'; // 输出白色块数量
}
return 0;
}